DSL 2 D Range Update Query - NISHIO Hirokazu's Scrapbox (Auto-translated from Japanese)

DSL 2 D Range Update Query

DSL_2_D Range Update Query

How should the "overwrite value" range action be defined?

The range action doesn't know which is later, whether the node is above or below.

So I made the value timestamped, and propagation downwards is a binary operation that "takes the one with the newer timestamp".

Alternative solution Propagation down the dual segment tree.

code:python

def main():

N, Q = map(int, input().split())

depth = N.bit_length() + 1

set_depth(depth)

action_unity = (-1, INF)

table = action_unity * SEGTREE_SIZE

for time in range(Q):

q, *args = map(int, input().split())

if q == 0:

# update

s, t, new_value = args

range_update(table, s, t + 1, lambda x: (time, new_value))

else:

# find

print(down_propagate_to_leaf(

table, args0, max, action_unity)1)

---

This page is auto-translated from /nishio/DSL 2 D Range Update Query. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.